#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <cctype>
#include<strstream>
#include <list>
#include "PKB.h"
#include "Affects.h"
#include "AffectsBip.h"
#include <time.h>
#include <set>

using namespace std;

struct node_t{
	string data;
	int left;
	int right;
};

typedef struct{
	string SelectType, SelectName;
	vector<string> tupleType, tupleName;
}selectQuery_t;

typedef struct{
	string FunctionType;
	string FirstElementName, FirstElementType;
	string SecondElementName, SecondElementType;
}funcQuery_t;

typedef struct{
	string ElementName, ElementType;
	string VarRef;
	vector<Pattern_node> Expression;
	bool isVarRefVariable; 
	bool ExpWithUnderscore;
}patternQuery_t;

typedef struct{
	string leftType; // Assign; While; stmt, prog_line->Statement; c->Constant; Integer; p->Procedure; v->Variable; String; 
	string leftName;
	string rightType;
	string rightName;
}compareQuery_t;

typedef struct{
	selectQuery_t selectQuery;
	vector<funcQuery_t> funcQueries;
	vector<patternQuery_t> patternQueries;
	vector<compareQuery_t> compareQueries;
	vector<string> callRelation;
}parsedQueries_t;

typedef struct{
	vector<vector<int>> table;
	vector<string> colName;
	string type;
	int numOfColumn;
}queryTreeNode_t;

class QueryProcessor{
private:
	//Variable passing by the constructor.
	pair<string, string> _query;
	PKB* pkb;
	vector<string> patternType;
	//Pre-processor variable
	string errors[10];
	parsedQueries_t queries;
	//Evaluator variable
	//bool isSelectLineNum;
	int selectType; // 1-line num, 2-variable, 3-boolean, 4-procedure, 5-tuple, 6-constant
	string selectedArgName;
	vector<queryTreeNode_t> queryTree;
	vector<string> commonCol;//for queryEvaluator use

	//Functions used by Pre-processor to parser the query
	bool queryParser();
	inline string trim(string&);
	void toLowerCase(string&);
	string filterDash(string);
	string filterQuote(string);
	string convertName(string name,map<string,string> args);
	void explode(string str, string separator, vector<string>* results);
	string capitalize(string str);
  	string& replace(string& str,const string& old_value,const string& new_value);
	int priority(char a);
	size_t findOp(string str);
	int is_digit (int c);
	string splitString(string input,int pos);
	string convertInt(int number);
	
	// Functions used by Pre-processor to build tables
	void buildTable();
	void buildSelect(selectQuery_t);
	void queryFollows(funcQuery_t);
	void queryFollowsStar(funcQuery_t);
	void queryParent(funcQuery_t);
	void queryParentStar(funcQuery_t);
	void queryModifies(funcQuery_t);
	void queryUses(funcQuery_t);
	void queryCall(funcQuery_t);
	void queryCallStar(funcQuery_t);
	void queryNext(funcQuery_t);
	void queryNextStar(funcQuery_t);
	void queryNextBip(funcQuery_t);
	void queryNextBipStar(funcQuery_t);
	void queryAffects(funcQuery_t);
	void queryAffectsStar(funcQuery_t);
	void queryAffectsBip(funcQuery_t);
	void queryAffectsBipStar(funcQuery_t);
	void queryContains(funcQuery_t);
	void queryContainsStar(funcQuery_t);
//	vector<TNode*> searchASTByType(TNode*, string);
//	vector<TNode*> searchASTByName(TNode*, int, string);
	void buildCallRelationTable(string);
	
	bool areIdentical(vector<Pattern_node>, int, vector<Pattern_node>, int);
	bool isSubtree(vector<Pattern_node>, int, vector<Pattern_node>, int);
	void queryPattern(patternQuery_t);
	
	void queryCompare(compareQuery_t);

	vector<string> findVarNames(vector<int>);
	bool hasVar(string, vector<string>, int, int);
	bool isInList(int, int, vector<pair<int,int>>);
	
	// Functions used by Query Evaluator
	queryTreeNode_t mergeTable(queryTreeNode_t,queryTreeNode_t);
	list<string> convert(vector<int>);
	list<string> convert(vector<string>);
	bool haveCommonFactor(queryTreeNode_t,queryTreeNode_t);
	void buildNodeIntoTree(int thisNode,vector<queryTreeNode_t> queryTree,vector<int>* inTree,vector<vector<int>>* orderTree,bool isInMajorTree,int majorCount,vector<vector<int>>* majorTreeList,int normalCount,vector<vector<int>>* normalTreeList);
	void orderOfMajorTree(int root,vector<vector<int>> orderTree,vector<int>* result);

	void computeAffects();
	void computeAffectsStar();
	
	void computeNextStar();

	void computeNextBipStar();

	AffectsBip affectsBip;

	void queryPreprocessor();
	list<string> queryEvaluator();
public:
	QueryProcessor();
	QueryProcessor(PKB*);
	list<string> processingQuery(string);
};